home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2004 April / Gamestar_61_2004-04_dvdb.iso / DVDStar / Editace / hltp.exe / {app} / Source Code / Zoners Half-Life Tools / hlbsp / tjunc.cpp < prev    next >
C/C++ Source or Header  |  2001-04-24  |  13KB  |  559 lines
  1. #include "bsp5.h"
  2.  
  3. typedef struct wvert_s
  4. {
  5.     vec_t           t;
  6.     struct wvert_s* prev;
  7.     struct wvert_s* next;
  8. }
  9. wvert_t;
  10.  
  11. typedef struct wedge_s
  12. {
  13.     struct wedge_s* next;
  14.     vec3_t          dir;
  15.     vec3_t          origin;
  16.     wvert_t         head;
  17. }
  18. wedge_t;
  19.  
  20. static int      numwedges;
  21. static int      numwverts;
  22. static int      tjuncs;
  23. static int      tjuncfaces;
  24.  
  25. #define MAX_WVERTS   0x40000
  26. #define MAX_WEDGES   0x20000
  27.  
  28. static wvert_t  wverts[MAX_WVERTS];
  29. static wedge_t  wedges[MAX_WEDGES];
  30.  
  31. //============================================================================
  32.  
  33. #define    NUM_HASH    1024
  34.  
  35. wedge_t*        wedge_hash[NUM_HASH];
  36.  
  37. static vec3_t   hash_min;
  38. static vec3_t   hash_scale;
  39.  
  40. static void     InitHash(const vec3_t mins, const vec3_t maxs)
  41. {
  42.     vec3_t          size;
  43.     vec_t           volume;
  44.     vec_t           scale;
  45.     int             newsize[2];
  46.  
  47.     VectorCopy(mins, hash_min);
  48.     VectorSubtract(maxs, mins, size);
  49.     memset(wedge_hash, 0, sizeof(wedge_hash));
  50.  
  51.     volume = size[0] * size[1];
  52.  
  53.     scale = sqrt(volume / NUM_HASH);
  54.  
  55.     newsize[0] = size[0] / scale;
  56.     newsize[1] = size[1] / scale;
  57.  
  58.     hash_scale[0] = newsize[0] / size[0];
  59.     hash_scale[1] = newsize[1] / size[1];
  60.     hash_scale[2] = newsize[1];
  61. }
  62.  
  63. static unsigned HashVec(const vec3_t vec)
  64. {
  65.     unsigned        h;
  66.  
  67.     h = hash_scale[0] * (vec[0] - hash_min[0]) * hash_scale[2] + hash_scale[1] * (vec[1] - hash_min[1]);
  68.     if (h >= NUM_HASH)
  69.     {
  70.         return NUM_HASH - 1;
  71.     }
  72.     return h;
  73. }
  74.  
  75. //============================================================================
  76.  
  77. static bool     CanonicalVector(vec3_t vec)
  78. {
  79.     if (VectorNormalize(vec))
  80.     {
  81.         if (vec[0] > NORMAL_EPSILON )
  82.         {
  83.             return true;
  84.         }
  85.         else if (vec[0] < -NORMAL_EPSILON )
  86.         {
  87.             VectorSubtract(vec3_origin, vec, vec);
  88.             return true;
  89.         }
  90.         else
  91.         {
  92.             vec[0] = 0;
  93.         }
  94.     
  95.         if (vec[1] > NORMAL_EPSILON )
  96.         {
  97.             return true;
  98.         }
  99.         else if (vec[1] < -NORMAL_EPSILON )
  100.         {
  101.             VectorSubtract(vec3_origin, vec, vec);
  102.             return true;
  103.         }
  104.         else
  105.         {
  106.             vec[1] = 0;
  107.         }
  108.  
  109.         if (vec[2] > NORMAL_EPSILON )
  110.         {
  111.             return true;
  112.         }
  113.         else if (vec[2] < -NORMAL_EPSILON )
  114.         {
  115.             VectorSubtract(vec3_origin, vec, vec);
  116.             return true;
  117.         }
  118.         else
  119.         {
  120.             vec[2] = 0;
  121.         }
  122. //        hlassert(false);
  123.         return false;
  124.     }
  125. //    hlassert(false);
  126.     return false;
  127. }
  128.  
  129. static wedge_t *FindEdge(const vec3_t p1, const vec3_t p2, vec_t* t1, vec_t* t2)
  130. {
  131.     vec3_t          origin;
  132.     vec3_t          dir;
  133.     wedge_t*        w;
  134.     vec_t           temp;
  135.     int             h;
  136.  
  137.     VectorSubtract(p2, p1, dir);
  138.     if (!CanonicalVector(dir))
  139.     {
  140. #if _DEBUG
  141.         Warning("CanonicalVector: degenerate @ (%4.3f %4.3f %4.3f )\n", p1[0], p1[1], p1[2]);
  142. #endif
  143.     }
  144.  
  145.     *t1 = DotProduct(p1, dir);
  146.     *t2 = DotProduct(p2, dir);
  147.  
  148.     VectorMA(p1, -*t1, dir, origin);
  149.  
  150.     if (*t1 > *t2)
  151.     {
  152.         temp = *t1;
  153.         *t1 = *t2;
  154.         *t2 = temp;
  155.     }
  156.  
  157.     h = HashVec(origin);
  158.  
  159.     for (w = wedge_hash[h]; w; w = w->next)
  160.     {
  161.         temp = w->origin[0] - origin[0];
  162.         if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  163.         {
  164.             continue;
  165.         }
  166.         temp = w->origin[1] - origin[1];
  167.         if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  168.         {
  169.             continue;
  170.         }
  171.         temp = w->origin[2] - origin[2];
  172.         if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  173.         {
  174.             continue;
  175.         }
  176.  
  177.         temp = w->dir[0] - dir[0];
  178.         if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  179.         {
  180.             continue;
  181.         }
  182.         temp = w->dir[1] - dir[1];
  183.         if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  184.         {
  185.             continue;
  186.         }
  187.         temp = w->dir[2] - dir[2];
  188.         if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  189.         {
  190.             continue;
  191.         }
  192.  
  193.         return w;
  194.     }
  195.  
  196.     hlassume(numwedges < MAX_WEDGES, assume_MAX_WEDGES);
  197.     w = &wedges[numwedges];
  198.     numwedges++;
  199.  
  200.     w->next = wedge_hash[h];
  201.     wedge_hash[h] = w;
  202.  
  203.     VectorCopy(origin, w->origin);
  204.     VectorCopy(dir, w->dir);
  205.     w->head.next = w->head.prev = &w->head;
  206.     w->head.t = 99999;
  207.     return w;
  208. }
  209.  
  210. /*
  211.  * ===============
  212.  * AddVert
  213.  * 
  214.  * ===============
  215.  */
  216. #define T_EPSILON    ON_EPSILON
  217.  
  218. static void     AddVert(const wedge_t* const w, const vec_t t)
  219. {
  220.     wvert_t*        v;
  221.     wvert_t*        newv;
  222.  
  223.     v = w->head.next;
  224.     do
  225.     {
  226.         if (fabs(v->t - t) < T_EPSILON)
  227.         {
  228.             return;
  229.         }
  230.         if (v->t > t)
  231.         {
  232.             break;
  233.         }
  234.         v = v->next;
  235.     }
  236.     while (1);
  237.  
  238.     // insert a new wvert before v
  239.     hlassume(numwverts < MAX_WVERTS, assume_MAX_WVERTS);
  240.  
  241.     newv = &wverts[numwverts];
  242.     numwverts++;
  243.  
  244.     newv->t = t;
  245.     newv->next = v;
  246.     newv->prev = v->prev;
  247.     v->prev->next = newv;
  248.     v->prev = newv;
  249. }
  250.  
  251. /*
  252.  * ===============
  253.  * AddEdge
  254.  * ===============
  255.  */
  256. static void     AddEdge(const vec3_t p1, const vec3_t p2)
  257. {
  258.     wedge_t*        w;
  259.     vec_t           t1;
  260.     vec_t           t2;
  261.  
  262.     w = FindEdge(p1, p2, &t1, &t2);
  263.     AddVert(w, t1);
  264.     AddVert(w, t2);
  265. }
  266.  
  267. /*
  268.  * ===============
  269.  * AddFaceEdges
  270.  * 
  271.  * ===============
  272.  */
  273. static void     AddFaceEdges(const face_t* const f)
  274. {
  275.     int             i, j;
  276.  
  277.     for (i = 0; i < f->numpoints; i++)
  278.     {
  279.         j = (i + 1) % f->numpoints;
  280.         AddEdge(f->pts[i], f->pts[j]);
  281.     }
  282. }
  283.  
  284. //============================================================================
  285.  
  286. static byte     superfacebuf[1024 * 16];
  287. static face_t*  superface = (face_t*)superfacebuf;
  288. static int      MAX_SUPERFACEEDGES = (sizeof(superfacebuf) - sizeof(face_t) + sizeof(superface->pts)) / sizeof(vec3_t);
  289. static face_t*  newlist;
  290.  
  291. static void     SplitFaceForTjunc(face_t* f, face_t* original)
  292. {
  293.     int             i;
  294.     face_t*         newface;
  295.     face_t*         chain;
  296.     vec3_t          dir, test;
  297.     vec_t           v;
  298.     int             firstcorner, lastcorner;
  299.  
  300. #ifdef _DEBUG
  301.     static int      counter = 0;
  302.  
  303.     Log("SplitFaceForTjunc %d\n", counter++);
  304. #endif
  305.  
  306.     chain = NULL;
  307.     do
  308.     {
  309.         hlassume(f->original == NULL, assume_ValidPointer);     // "SplitFaceForTjunc: f->original"
  310.  
  311.         if (f->numpoints <= MAXPOINTS)
  312.         {                                                  // the face is now small enough without more cutting
  313.             // so copy it back to the original
  314.             *original = *f;
  315.             original->original = chain;
  316.             original->next = newlist;
  317.             newlist = original;
  318.             return;
  319.         }
  320.  
  321.         tjuncfaces++;
  322.  
  323. restart:
  324.         // find the last corner 
  325.         VectorSubtract(f->pts[f->numpoints - 1], f->pts[0], dir);
  326.         VectorNormalize(dir);
  327.         for (lastcorner = f->numpoints - 1; lastcorner > 0; lastcorner--)
  328.         {
  329.             VectorSubtract(f->pts[lastcorner - 1], f->pts[lastcorner], test);
  330.             VectorNormalize(test);
  331.             v = DotProduct(test, dir);
  332.             if (v < 1.0 - ON_EPSILON || v > 1.0 + ON_EPSILON)
  333.             {
  334.                 break;
  335.             }
  336.         }
  337.  
  338.         // find the first corner        
  339.         VectorSubtract(f->pts[1], f->pts[0], dir);
  340.         VectorNormalize(dir);
  341.         for (firstcorner = 1; firstcorner < f->numpoints - 1; firstcorner++)
  342.         {
  343.             VectorSubtract(f->pts[firstcorner + 1], f->pts[firstcorner], test);
  344.             VectorNormalize(test);
  345.             v = DotProduct(test, dir);
  346.             if (v < 1.0 - ON_EPSILON || v > 1.0 + ON_EPSILON)
  347.             {
  348.                 break;
  349.             }
  350.         }
  351.  
  352.         if (firstcorner + 2 >= MAXPOINTS)
  353.         {
  354.             // rotate the point winding
  355.             VectorCopy(f->pts[0], test);
  356.             for (i = 1; i < f->numpoints; i++)
  357.             {
  358.                 VectorCopy(f->pts[i], f->pts[i - 1]);
  359.             }
  360.             VectorCopy(test, f->pts[f->numpoints - 1]);
  361.             goto restart;
  362.         }
  363.  
  364.         // cut off as big a piece as possible, less than MAXPOINTS, and not
  365.         // past lastcorner
  366.  
  367.         newface = NewFaceFromFace(f);
  368.  
  369.         hlassume(f->original == NULL, assume_ValidPointer);     // "SplitFaceForTjunc: f->original"
  370.  
  371.         newface->original = chain;
  372.         chain = newface;
  373.         newface->next = newlist;
  374.         newlist = newface;
  375.         if (f->numpoints - firstcorner <= MAXPOINTS)
  376.         {
  377.             newface->numpoints = firstcorner + 2;
  378.         }
  379.         else if (lastcorner + 2 < MAXPOINTS && f->numpoints - lastcorner <= MAXPOINTS)
  380.         {
  381.             newface->numpoints = lastcorner + 2;
  382.         }
  383.         else
  384.         {
  385.             newface->numpoints = MAXPOINTS;
  386.         }
  387.  
  388.         for (i = 0; i < newface->numpoints; i++)
  389.         {
  390.             VectorCopy(f->pts[i], newface->pts[i]);
  391.         }
  392.  
  393.         for (i = newface->numpoints - 1; i < f->numpoints; i++)
  394.         {
  395.             VectorCopy(f->pts[i], f->pts[i - (newface->numpoints - 2)]);
  396.         }
  397.         f->numpoints -= (newface->numpoints - 2);
  398.     }
  399.     while (1);
  400.  
  401. }
  402.  
  403. /*
  404.  * ===============
  405.  * FixFaceEdges
  406.  * 
  407.  * ===============
  408.  */
  409. static void     FixFaceEdges(face_t* f)
  410. {
  411.     int             i;
  412.     int             j;
  413.     int             k;
  414.     wedge_t*        w;
  415.     wvert_t*        v;
  416.     vec_t           t1;
  417.     vec_t           t2;
  418.  
  419.     *superface = *f;
  420.  
  421. restart:
  422.     for (i = 0; i < superface->numpoints; i++)
  423.     {
  424.         j = (i + 1) % superface->numpoints;
  425.  
  426.         w = FindEdge(superface->pts[i], superface->pts[j], &t1, &t2);
  427.  
  428.         for (v = w->head.next; v->t < t1 + T_EPSILON; v = v->next)
  429.         {
  430.         }
  431.  
  432.         if (v->t < t2 - T_EPSILON)
  433.         {
  434.             tjuncs++;
  435.             // insert a new vertex here
  436.             for (k = superface->numpoints; k > j; k--)
  437.             {
  438.                 VectorCopy(superface->pts[k - 1], superface->pts[k]);
  439.             }
  440.             VectorMA(w->origin, v->t, w->dir, superface->pts[j]);
  441.             superface->numpoints++;
  442.             hlassume(superface->numpoints < MAX_SUPERFACEEDGES, assume_MAX_SUPERFACEEDGES);
  443.             goto restart;
  444.         }
  445.     }
  446.  
  447.     if (superface->numpoints <= MAXPOINTS)
  448.     {
  449.         *f = *superface;
  450.         f->next = newlist;
  451.         newlist = f;
  452.         return;
  453.     }
  454.  
  455.     // the face needs to be split into multiple faces because of too many edges
  456.  
  457.     SplitFaceForTjunc(superface, f);
  458.  
  459. }
  460.  
  461. //============================================================================
  462.  
  463. static void     tjunc_find_r(node_t* node)
  464. {
  465.     face_t*         f;
  466.  
  467.     if (node->planenum == PLANENUM_LEAF)
  468.     {
  469.         return;
  470.     }
  471.  
  472.     for (f = node->faces; f; f = f->next)
  473.     {
  474.         AddFaceEdges(f);
  475.     }
  476.  
  477.     tjunc_find_r(node->children[0]);
  478.     tjunc_find_r(node->children[1]);
  479. }
  480.  
  481. static void     tjunc_fix_r(node_t* node)
  482. {
  483.     face_t*         f;
  484.     face_t*         next;
  485.  
  486.     if (node->planenum == PLANENUM_LEAF)
  487.     {
  488.         return;
  489.     }
  490.  
  491.     newlist = NULL;
  492.  
  493.     for (f = node->faces; f; f = next)
  494.     {
  495.         next = f->next;
  496.         FixFaceEdges(f);
  497.     }
  498.  
  499.     node->faces = newlist;
  500.  
  501.     tjunc_fix_r(node->children[0]);
  502.     tjunc_fix_r(node->children[1]);
  503. }
  504.  
  505. /*
  506.  * ===========
  507.  * tjunc
  508.  * 
  509.  * ===========
  510.  */
  511. void            tjunc(node_t* headnode)
  512. {
  513.     vec3_t          maxs, mins;
  514.     int             i;
  515.  
  516.     Verbose("---- tjunc ----\n");
  517.  
  518.     if (g_notjunc)
  519.     {
  520.         return;
  521.     }
  522.  
  523.     //
  524.     // identify all points on common edges
  525.     //
  526.  
  527.     // origin points won't allways be inside the map, so extend the hash area 
  528.     for (i = 0; i < 3; i++)
  529.     {
  530.         if (fabs(headnode->maxs[i]) > fabs(headnode->mins[i]))
  531.         {
  532.             maxs[i] = fabs(headnode->maxs[i]);
  533.         }
  534.         else
  535.         {
  536.             maxs[i] = fabs(headnode->mins[i]);
  537.         }
  538.     }
  539.     VectorSubtract(vec3_origin, maxs, mins);
  540.  
  541.     InitHash(mins, maxs);
  542.  
  543.     numwedges = numwverts = 0;
  544.  
  545.     tjunc_find_r(headnode);
  546.  
  547.     Verbose("%i world edges  %i edge points\n", numwedges, numwverts);
  548.  
  549.     //
  550.     // add extra vertexes on edges where needed
  551.     //
  552.     tjuncs = tjuncfaces = 0;
  553.  
  554.     tjunc_fix_r(headnode);
  555.  
  556.     Verbose("%i edges added by tjunctions\n", tjuncs);
  557.     Verbose("%i faces added by tjunctions\n", tjuncfaces);
  558. }
  559.